import sys
sys.path.append('../列表查找/')
from run_time import *
import random

"""
下面这个算法的复杂度为：O(n)*(O(n)+O(n))=2*n**2
"""


@run_time
def select_sort_one(li):
    a = []
    for x in range(len(li)):
        min_nub = min(li)
        a.append(min_nub)
        li.remove(min_nub)
    return a


"""
下面这个select sort 的复杂度为O(n**2)
"""


@run_time
def select_sort_two(li):
    for x in range(len(li)):
        min_val = x
        for j in range(x+1, len(li)):
            if li[j] < li[min_val]:
                li[j], li[min_val] = li[min_val], li[j]
    return li


agfa = list(range(10000))
random.shuffle(agfa)
print(agfa)
print(select_sort_one(agfa))  # 低级排序

agfb = list(range(10000))
random.shuffle(agfb)
print(agfb)
print(select_sort_two(agfb))  # 优化之后的选择排序
